题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

官方题解

暴力法

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

时间复杂度：O(n^2)O(n2)，对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)O(n2)。
空间复杂度：O(1)O(1)。

两遍哈希表

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

时间复杂度：O(n)O(n)，我们把包含有 nn 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1)O(1) ，所以时间复杂度为 O(n)O(n)。
空间复杂度：O(n)O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 nn 个元素。

一遍哈希表

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

时间复杂度：O(n)O(n)，我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。
空间复杂度：O(n)O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn 个元素。

知识总结

ArrayList与HashMap索引的机制

让我们来看看ArrayList的indexOf()方法的源码：

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1; 
}
public int lastIndexOf(Object o) {
  if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

再看看HashMap方法的get()与containsKey()方法的源码：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

很清楚可以看出来，ArrayList的索引其实就是按顺序遍历集合进行查找，而HashMap的索引用的是哈希表(网上说的，我暂时没看懂)，可见，对于需要查找数组中某一元素是否存在这一需求，最好的方式就是将数组转换为HashMap来存储，若转换成ArrayList那跟暴力求解区别不大。

将数组转换为ArrayList的方法

https://blog.csdn.net/sinat_29355599/article/details/81606908

https://blog.csdn.net/x541211190/article/details/79597236

总的来说，有两种方式：

ArrayList<Element> arrayList = new ArrayList<Element>(Arrays.asList(array));


ArrayList<String> arrayList = new ArrayList<String>(array.length);
Collections.addAll(arrayList, array);

其中，Arrays.asList(array)方法返回值类型ArrayList不是通用的ArrayList类，它是数组的列表视图，定长，即无法add()。而且，它接受的是泛型参数，即如果传入int[]数组，它将会将整个数组视为一个参数，而不是数组中的整数，解决方式是改为Integer[]。详见<https://blog.csdn.net/qq_34115899/article/details/80513271>

而第二章方式采用的是将数组中的元素转换为二进制再添加到List中，效率最高，而且没有上述坑，故尽可能采用第二种方式。